package problem207_Course_Schedule;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;

public class Solution2 {
	public boolean canFinish(int numCourses, int[][] prerequisites) {
		Map<Integer,List<Integer>> graph=new HashMap<>();
		int[] inDegree=new int[numCourses];
		for(int[] s:prerequisites){
			if(graph.containsKey(s[1])){
				graph.get(s[1]).add(s[0]);
			}else{
				graph.put(s[1], new LinkedList<>());
				graph.get(s[1]).add(s[0]);
			}
			inDegree[s[0]]++;
		}
		Queue<Integer> queue=new LinkedList<>();
		for(int i=0;i<inDegree.length;i++){
			if(inDegree[i]==0){
				queue.add(i);
			}
		}
		int visited=0;
		while(!queue.isEmpty()){
			int top=queue.poll();
			visited++;
			List<Integer> adj=graph.get(top);
			if(adj!=null){
				for(int i:adj){
					inDegree[i]--;
					if(inDegree[i]==0){
						queue.add(i);
					}
				}
			}
		}
		return visited==numCourses;
	}
}
